package org.lintcode_Pattern;

/**
 * @Auther: qingle
 * @Date: 2024/8/20-22:38
 * @Description:
 *
 * 复杂度
 * • 时间复杂度：
 * ￮ 快速排序(期望复杂度) ： O(nlogn)
 * ￮ 归并排序(最坏复杂度) ： O(nlogn)
 * • 空间复杂度：
 * ￮ 快速排序 ： O(1)
 * ￮ 归并排序 ： O(n)
 * 炼码例题
 * • LintCode 464. 整数排序 II
 * @version: 1.0
 */
public class A3排序算法 {

	// 快速排序

	/**
	 * 在快速排序中，我们选择一个枢轴（pivot），然后重新排列数组，
	 * 使得所有比枢轴小的元素都在它的左边，所有比枢轴大的元素都在它的右边。
	 * 然后递归地对左右两个子数组进行同样的操作。
	 * @param A
	 */
	public void sortIntegers(int[] A) {
		quickSort(A, 0, A.length - 1);
	}

	private void quickSort(int[] A, int start, int end) {
		if (start >= end) {
			return;
		}
		int left = start, right = end;
		int pivot = A[(start + end) / 2];

		while (left <= right) {
			while (left <= right && A[left] < pivot) {
				left++;
			}
			while (left <= right && A[right] > pivot) {
				right--;
			}
			if (left <= right) {
				int temp = A[left];
				A[left] = A[right];
				A[right] = temp;
				left++;
				right--;
			}
		}
		quickSort(A, start, right);
		quickSort(A, left, end);
	}


	// 归并排序

	/**
	 * 在归并排序中，我们把数组分成两半，对每一半进行排序，然后将排序好的两半合并在一起。
	 * 合并操作是将两个有序数组合并成一个有序数组的过程。
	 * @param A
	 */

	public void sortIntegers2(int[] A) {
		if (A == null || A.length == 0) {
			return;
		}
		int[] temp = new int[A.length];
		mergeSort(A, 0, A.length - 1, temp);
	}

	private void mergeSort(int[] A, int start, int end, int[] temp) {
		if (start >= end) {
			return;
		}
		mergeSort(A, start, (start + end) / 2, temp);
		mergeSort(A, (start + end) / 2 + 1, end, temp);
		merge(A, start, end, temp);
	}

	private void merge(int[] A, int start, int end, int[] temp) {
		int middle = (start + end) / 2;
		int leftIndex = start;
		int rightIndex = middle + 1;
		int index = start;

		while (leftIndex <= middle && rightIndex <= end) {
			if (A[leftIndex] < A[rightIndex]) {
				temp[index++] = A[leftIndex++];
			} else {
				temp[index++] = A[rightIndex++];
			}
		}

		while (leftIndex <= middle) {
			temp[index++] = A[leftIndex++];
		}
		while (rightIndex <= end) {
			temp[index++] = A[rightIndex++];
		}

		if (end + 1 - start >= 0)
			System.arraycopy(temp, start, A, start, end + 1 - start);
	}

}
